class Solution
{
public:
    int longestIdealString(string s, int k)
    {
        vector<int> dp(26, 0);
        for (char c : s)
        {
            int maxSubLen = dp[c - 'a'];
            char lower = max(0 + 'a', c - k);
            char upper = min(0 + 'z', c + k);
            for (char nearChar = lower; nearChar <= upper; ++nearChar)
            {
                maxSubLen = max(maxSubLen, dp[nearChar - 'a'] + 1);
            }
            dp[c - 'a'] = maxSubLen;
        }
        return *max_element(dp.begin(), dp.end());
    }
};